#include <string.h>
#include <list>
#include <vector>
#include <queue>

struct GraphEdge;
struct GraphVertex
{
    int iMark, iInd;
    GraphEdge *edge;
    char m_lpbtData[24];
    GraphVertex(char *lpbtData)
    {
        edge = NULL;
        iMark = 0;
        strcpy(m_lpbtData, lpbtData);
    }
};
struct GraphEdge
{
    GraphEdge *next, *prev, *opps;
    GraphVertex *vertex;
    GraphEdge()
    {
        next = NULL;
        prev = NULL;
        opps = NULL;
        vertex = NULL;
    }
};

class CGraph
{
public:
    std::list<GraphVertex> vertices;
    std::list<GraphEdge> edges;
    GraphVertex* add_vertex(char *lpbtData)
    {
        vertices.push_back(GraphVertex(lpbtData));
        return &(*(vertices.rbegin()));
    }
    GraphEdge* add_edge(GraphVertex*lpvt1, GraphVertex*lpvt2)
    {
        GraphEdge *edge;
        GraphEdge *edge_i, *edge_j;
        edge = exist_edge(lpvt1, lpvt2);
        if(edge == NULL)
        {
            edges.push_back(GraphEdge());
            edge_i = &(*edges.rbegin());
            edges.push_back(GraphEdge());
            edge_j = &(*edges.rbegin());
            edge_i->opps = edge_j;
            edge_j->opps = edge_i;
            edge_i->vertex = lpvt1;
            edge_j->vertex = lpvt2;
            if(edge_i->vertex->edge == NULL)
            {
                edge_i->vertex->edge = edge_i;
                edge_i->next = edge_j;
                edge_j->prev = edge_i;
            }
            else
            {
                edge_i->next = edge_i->vertex->edge->next;
                edge_i->vertex->edge->next->prev = edge_i;
                edge_j->prev = edge_i->vertex->edge;
                edge_i->vertex->edge->next = edge_j;
            }
            if(edge_j->vertex->edge == NULL)
            {
                edge_j->vertex->edge = edge_j;
                edge_j->next = edge_i;
                edge_i->prev = edge_j;
            }
            else
            {
                edge_j->next = edge_j->vertex->edge->next;
                edge_j->vertex->edge->next->prev = edge_j;
                edge_i->prev = edge_j->vertex->edge;
                edge_j->vertex->edge->next = edge_i;
            }
            edge = edge_j;
        }
        return edge;
    }
    void clear()
    {
        vertices.clear();
        edges.clear();
    }
    GraphEdge* exist_edge(GraphVertex*lpvt1, GraphVertex*lpvt2)
    {
        GraphEdge *edge;
        GraphEdge *edge0, *edge1;
        edge = NULL;
        if(!(lpvt1->edge == 0 || lpvt2->edge == 0))
        {
            edge0 = lpvt1->edge->opps;
            edge1 = edge0;
            do
            {
                if(edge1->vertex == lpvt2)
                {
                    edge = edge1;
                }
                edge1 = edge1->opps->next;
            }while(!(edge0 == edge1 || edge == NULL));
        }
        return edge;
    }
    GraphVertex* search_vertex(GraphVertex *lpvtStart, char *lpstrStatus)
    {
        std::vector<GraphVertex*> vecvtSearched;
        std::queue<GraphVertex*> quvtSeed;
        GraphEdge *edge0, *edge1;
        GraphVertex *lpvtSeed, *lpvtRusult, *lpvtVertex;
        lpvtRusult = NULL;
        if (strcmp(lpvtStart->m_lpbtData, lpstrStatus) == 0)
        {
            lpvtRusult = lpvtStart;
        }
        else
        {
            lpvtStart->iMark = 1;
            quvtSeed.push(lpvtStart);
            vecvtSearched.push_back(lpvtStart);
        }
        while (!quvtSeed.empty())
        {
            lpvtSeed = quvtSeed.front();
            quvtSeed.pop();
            if (lpvtSeed->edge != NULL)
            {
                edge0 = lpvtSeed->edge->opps;
                edge1 = edge0;
                do
                {
                    lpvtVertex = edge1->vertex;
                    if (lpvtVertex->iMark == 0)
                    {
                        if (strcmp(lpvtVertex->m_lpbtData, lpstrStatus) == 0)
                        {
                            lpvtRusult = lpvtVertex;
                            while (!quvtSeed.empty())
                            {
                                quvtSeed.pop();
                            }
                        }
                        else
                        {
                            lpvtVertex->iMark = 1;
                            quvtSeed.push(lpvtVertex);
                            vecvtSearched.push_back(lpvtVertex);
                        }
                    }
                    edge1 = edge1->opps->next;
                } while (edge1 != edge0 && lpvtRusult == NULL);
            }
        }
        while (!vecvtSearched.empty())
        {
            lpvtVertex = (*(vecvtSearched.rbegin()));
            lpvtVertex->iMark = 0;
            vecvtSearched.pop_back();
        }
        return lpvtRusult;
    }
    GraphVertex* round_search(GraphVertex *lpvtStart, char *lpstrStatus)
    {
        GraphVertex *lpvtResult;
        GraphEdge *edge0, *edge1;
        lpvtResult = NULL;
        if (lpvtStart->edge != NULL)
        {
            edge0 = lpvtStart->edge->opps;
            edge1 = edge0;
            do
            {
                if (strcmp(edge1->vertex->m_lpbtData, lpstrStatus) == 0)
                {
                    lpvtResult = edge1->vertex;
                }
                edge1 = edge1->opps->next;
            } while (edge1 != edge0 && lpvtResult == NULL);
        }
        return lpvtResult;
    }
    GraphVertex* range_search(char *lpstrStatus, int iMinInd)
    {
        std::list<GraphVertex>::reverse_iterator ri;
        GraphVertex *lpvtResult;
        if (iMinInd < 0)
        {
            iMinInd = 0;
        }
        lpvtResult = NULL;
        for (ri = vertices.rbegin(); (ri != vertices.rend() && ri->iInd >= iMinInd && lpvtResult == NULL); ++ri)
        {
            if (strcmp(ri->m_lpbtData, lpstrStatus) == 0)
            {
                lpvtResult = &(*ri);
            }
        }
        return lpvtResult;
    }
};

